Cryptographic systems are widely used to ensure the privacy and authenticity of messages communicated over insecure channels. In many applications, it is necessary that encryption be performed at high data rates, a requirement usually achieved, if at all, with the help of supporting cryptographic hardware. Such hardware, however is not available on most conventional computer systems. Moreover, it has been found that an algorithm designed to run well in hardware does not perform in software as well as an algorithm optimized for software execution.
A stream cipher (or pseudorandom generator) is an algorithm that takes a short random string, and expands it into a much longer string, that still “looks random” to adversaries with limited resources. The short input string is called the seed (or key) of the cipher, and the long output string is called the output stream (or key-stream). Stream ciphers can be used for shared-key encryption, by using the output stream as a one-time-pad. Examples of systems using a stream cipher are given in U.S. Pat. No. 5,454,039 issued to Coppersmith et al. on Sep. 26, 1995 and U.S. Pat. No. 5,835,597 issued to Coppersmith et al. On Nov. 10, 1998. These patents are herein incorporated by reference in their entirety.
An example flow diagram 100 of a prior art usage of stream ciphers is given in FIG. 1. In the system flow 100, a sender system 110 attempts to send a plaintext message 116 to a receiving system 111. To hide the plaintext from eavesdroppers, the sender 110 and the receiver 111 share a secret key 112. They may also share another string 113, which need not be secret (e.g., a counter value, that holds the value 1 for the first such plaintext message 116, the value 2 for the second message, etc.). The string 113 is usually called an IV (for Initial Value).
The sender 110 inputs the key 112 and the IV 113 to a stream cipher function 114. The output of the stream cipher function is an output stream 115. This output stream 115 is combined with plain text message 116 to produce encrypted ciphertext 117. (This combination is usually as simple as bitwise exclusive-OR, although it can be a different or even more complicated operation.) The ciphertext 117 is then sent to the receiving system, possibly over an insecure 15 communication channel. The receiving system 111 can then convert the ciphertext 117 back to plaintext 116. The receiving system does this by producing an identical output stream 115 using the key 112 and IV 113. This output stream 115 at the receiving system 111 is combined with the ciphertext 117 to produce the plaintext 116.
A more detailed explanation of stream ciphers is given in Chapter 6 of A. Menezes, P. Van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996 which is herein incorporated by reference in its entirety.
FIG. 2 is a flow chart of a typical prior art stream cipher 200. The stream cipher 200 typically maintains some secret state 204, which is obtained from an initial key 201 (and possibly an IV 202) via an initialization function 203. In each of one or more steps, the state 204 is modified by a round-function 205. The output 207 of each of the steps is computed from the current state via an output-function 206. The output stream 208 is the concatenation of the outputs 207 from all the steps.
SEAL (Software Efficient ALgorithm) is a stream cipher that was designed in 1992 by Rogaway and Coppersmith, specifically for the purpose of obtaining a software efficient stream cipher. Nearly ten years after it was designed, SEAL is still the fastest steam cipher for software implementations on contemporary PC's, with “C” implementations running at 5 cycle/byte on common PC's (and 3.5 cycle/byte on some RISC workstations). A description of SEAL is found in U.S. Pat. No. 5,454,039 cited above and P. Rogaway and D. Coppersmith, “A software optimized encryption algorithm”, Journal of Cryptology, 11(4), pages 273–287, 1998, which is herein incorporated by reference in its entirety.
In SEAL, the “round function” 205 is similar to round functions of typical block ciphers, and the “output function” 206 is simply a masking operation, where the current state is combined (via integer addition) with values from some fixed secret tables.
In terms of security, SEAL is somewhat of a mixed story. Recently, Fluhrer described an attack on SEAL 3.0, that can distinguish the output stream from random after about 244 output bytes. See S. Fluhrer, “Cryptanalysis of the SEAL 3.0 pseudorandom function family”, “Proceedings of the Fast Software Encryption Workshop” (FSE '01), 2001 which is herein incorporated by reference in its entirety.
As with most ciphers, there is a trade off between the speed and security of the ciphers. Therefore, there is a need in the prior art to gain more secure ciphers with the same (or faster) speeds or gain faster speeds without losing security.